
package com.ting.test.algorithms.递归和动态规划.从左往右的模型;

/**
 * arr是面值数组，其中的值都是正数且没有重复。再给定一个正数aim。
 * 每个值都认为是一种面值，且认为张数是无限的。
 * 返回组成aim的最少货币数
 */
public class 不同面值货币问题3 {

    public static void main(String[] args) {
        int[] arr = new int[]{1, 1, 1, 1, 3, 4, 4, 3, 2, 2, 2, 5, 5, 5};//货币
        int aim = 20;//目标金额
        int count = numbers(arr, aim);
    }

    private static int numbers(int[] arr, int aim) {
        if (arr == null || aim < 0) {
            return 0;
        }

        // 根据题意  主函数调用，从0位置开始，要求拼装aim元需要的最小张数
        return process(arr, 0, aim); //暴力递归方案
//        return dp(arr, aim);
    }

    /**
     * @param arr   货币数组
     * @param index 从哪个位置的货币开始
     * @param rest  目标金额
     * @return 返回从index位置的元素开始，要拼装aim的最小张数
     */
    private static int process(int[] arr, int index, int rest) {
        //base case
        if (index == arr.length) {
            //如果货币都已经用完了 恰好rest等于0 则说明当前的方案是可行的，
            //对于本题而言，要返回的是最小张数，那么在当前递归中没有用一张,因此返回0
            //如果货币都用完了，但是rest还不等于0，则说明该方案无效，返回MAX_VALUE
            return rest == 0 ? 0 : Integer.MAX_VALUE;
        }
        // 正对当前位置 有两种选择，当前货币要或者不要
        //总的方案个数，应该是这两种情况下方案的总和
        //这里和上一道题不一样的地方在于，这里的每一种面值货币，都有无数张，因此，每个位置都有很多中方案
        // 但是有一个隐藏的边界条件，那就是 每一中货币的张数和面值的累加和不能超过目标金额
        int ways = Integer.MAX_VALUE;
        int p;
        for (int i = 0; (arr[index] * i) < rest; i++) {
            p = process(arr, index + 1, rest - (arr[index] * i));
            ways = Math.min(ways, p + i);//注意 本次process（）的张数是当前index位置用掉的货币加index之后所有位置的货币使用的张数
            //当前递归只考虑当前及以后的情况，别想太多了
        }
        return ways;

    }

    /**
     * @param arr 货币数组
     * @param aim 目标金额
     * @return 返回从index位置的元素开始，要拼装aim的最小张数
     */
    private static int dp(int[] arr, int aim) {
        int N = arr.length;
        int[][] dp = new int[N + 1][aim + 1];//dp数组的每一个元素代表的是在(index,aim) 下的所有方案个数

        //根据process()的base case 可知 当前index==N 且 rest==0时，才能认为是一种方案，返回1  其他都是0
        // 对应到dp数组  只有  dp[N][0]=0;其余都无效方案
        dp[N][0] = 1;
        for (int i = 1; i < dp[0].length; i++) {
            dp[N][i] = Integer.MAX_VALUE;
        }

        //根据process() 我们发现，dp[index]的值总是依赖dpp[index+1]位置的值，且根据上面我们已经求出了dp[N]位置的值，
        //因此我们只需要倒着求就行了
        for (int index = N - 1; index >= 0; index--) {
            for (int rest = 0; rest <= aim; rest++) {
                int ways = Integer.MAX_VALUE;
                int p;
                for (int i = 0; (arr[index] * i) < rest; i++) {
                    p = dp[index + 1][rest - (arr[index] * i)];
                    ways = Math.min(ways, p + i);//注意 本次process（）的张数是当前index位置用掉的货币加index之后所有位置的货币使用的张数
                    //当前递归只考虑当前及以后的情况，别想太多了
                }
                dp[index][rest] = Math.min(dp[index][rest - arr[index] + 1], dp[index + 1][rest]);//一定要画图!!!
            }
        }
        return dp[0][aim];

    }

    /**
     * @param arr 货币数组
     * @param aim 目标金额
     * @return 返回从index位置的元素开始，要拼装aim的最小张数
     */
    private static int dp2(int[] arr, int aim) {
        int N = arr.length;
        int[][] dp = new int[N + 1][aim + 1];//dp数组的每一个元素代表的是在(index,aim) 下的所有方案个数

        //根据process()的base case 可知 当前index==N 且 rest==0时，才能认为是一种方案，返回1  其他都是0
        // 对应到dp数组  只有  dp[N][0]=0;其余都无效方案
        dp[N][0] = 1;
        for (int i = 1; i < dp[0].length; i++) {
            dp[N][i] = Integer.MAX_VALUE;
        }

        //根据process() 我们发现，dp[index]的值总是依赖dpp[index+1]位置的值，且根据上面我们已经求出了dp[N]位置的值，
        //因此我们只需要倒着求就行了
        for (int index = N - 1; index >= 0; index--) {
            for (int rest = 0; rest < aim; rest++) {
                int ways = Integer.MAX_VALUE;
                int p;
                for (int i = 0; (arr[index] * i) < rest; i++) {
                    p = dp[index + 1][rest - (arr[index] * i)];
                    ways = Math.min(ways, p + i);//注意 本次process（）的张数是当前index位置用掉的货币加index之后所有位置的货币使用的张数
                    //当前递归只考虑当前及以后的情况，别想太多了
                }
                dp[index][rest] = ways;
            }
        }
        return dp[0][aim];

    }

}

